{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Three Equal Parts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: threeEqualParts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #三等分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个由 <code>0</code> 和 <code>1</code> 组成的数组<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;，将数组分成 &nbsp;<strong>3&nbsp;个非空的部分</strong> ，使得所有这些部分表示相同的二进制值。</p>\n",
    "\n",
    "<p>如果可以做到，请返回<strong>任何</strong>&nbsp;<code>[i, j]</code>，其中 <code>i+1 &lt; j</code>，这样一来：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr[0], arr[1], ..., arr[i]</code>&nbsp;为第一部分；</li>\n",
    "\t<li><code>arr[i + 1], arr[i + 2], ..., arr[j - 1]</code>&nbsp;为第二部分；</li>\n",
    "\t<li><code>arr[j], arr[j + 1], ..., arr[arr.length - 1]</code>&nbsp;为第三部分。</li>\n",
    "\t<li>这三个部分所表示的二进制值相等。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果无法做到，就返回&nbsp;<code>[-1, -1]</code>。</p>\n",
    "\n",
    "<p>注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，<code>[1,1,0]</code>&nbsp;表示十进制中的&nbsp;<code>6</code>，而不会是&nbsp;<code>3</code>。此外，前导零也是<strong>被允许</strong>的，所以&nbsp;<code>[0,1,1]</code> 和&nbsp;<code>[1,1]</code>&nbsp;表示相同的值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,0,1,0,1]\n",
    "<strong>输出：</strong>[0,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,0,1,1]\n",
    "<strong>输出：</strong>[-1,-1]</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,0,0,1]\n",
    "<strong>输出：</strong>[0,2]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= arr.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>arr[i]</code>&nbsp;是&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [three-equal-parts](https://leetcode.cn/problems/three-equal-parts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [three-equal-parts](https://leetcode.cn/problems/three-equal-parts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,0,1]', '[1,1,0,1,1]', '[1,1,0,0,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        if s == 0:\n",
    "            return [0, 2]\n",
    "\n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    # 第一个1\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    # 第一个1到1总数的三分之一的位置，即第二部分的起始\n",
    "                    second = i\n",
    "                elif cur == 2 * partial:\n",
    "                    # 第三部分的起始，固定\n",
    "                    third = i\n",
    "                cur += 1\n",
    "\n",
    "        n = len(arr)\n",
    "        length = n - third\n",
    "        if first + length <= second and second + length <= third:\n",
    "            i = 0\n",
    "            # 以下用于判断三段位置是否相等\n",
    "            while third + i < n:\n",
    "                if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + length - 1, second + length]\n",
    "        return [-1, -1]\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/three-equal-parts/solutions/1862579/san-deng-fen-by-leetcode-solution-3l2y/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "\n",
    "# 总结：审题很重要，好的审题可以得到很好的思路，解决办法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        if s == 0:\n",
    "            return [0, 2]\n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == 2 * partial:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "        n = len(arr)\n",
    "        length = n - third\n",
    "        if first + length <= second and second + length <= third:\n",
    "            i = 0\n",
    "            while i < length:\n",
    "                if arr[first + i] != arr[second + i] or arr[second + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + length - 1, second + length]\n",
    "        return [-1, -1]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        if s == 0:\n",
    "            return [0, 2]\n",
    "\n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == 2 * partial:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "\n",
    "        n = len(arr)\n",
    "        length = n - third\n",
    "        if first + length <= second and second + length <= third:\n",
    "            i = 0\n",
    "            while third + i < n:\n",
    "                if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + length - 1, second + length]\n",
    "        return [-1, -1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s%3:\n",
    "            return [-1,-1]\n",
    "        if s==0:\n",
    "            return [0,2]\n",
    "        \n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == 2 * partial:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "\n",
    "        n = len(arr)\n",
    "        length = n - third\n",
    "        if first + length <= second and second + length <= third:\n",
    "            i = 0\n",
    "            while third + i < n:\n",
    "                if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + length - 1, second + length]\n",
    "        return [-1, -1]     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        one_num = 0\n",
    "        for x in arr:\n",
    "            one_num += x\n",
    "        if one_num % 3 != 0:\n",
    "            return [-1,-1]\n",
    "        p = one_num // 3\n",
    "        n = len(arr)\n",
    "        # 从给定末端开始倒叙寻找到1的总数目首次等于 one_num // 3 的下标\n",
    "        def get_idx(n:int)->int:\n",
    "            c3 = 0\n",
    "            p3 = 0\n",
    "            for i in range(n-1,-1,-1):\n",
    "                c3 += arr[i]\n",
    "                if c3 == p:\n",
    "                    p3 = i\n",
    "                    return p3\n",
    "        p3 = get_idx(n)\n",
    "        p2 = get_idx(p3)\n",
    "        p1 = get_idx(p2)\n",
    "        # 数组必须不能小于末端长度的3倍，因为1的总数目必须三等分\n",
    "        if (n-p3) * 3 > n:\n",
    "            return [-1,-1]\n",
    "        # 三个指针分别指向所在段的首个1的下标\n",
    "        i,j,k = p1,p2,p3\n",
    "        while i < p2 and j < p3 and k < n:\n",
    "            if arr[i] != arr[j] or arr[i] != arr[k] or arr[j] != arr[k]:\n",
    "                return [-1,-1]\n",
    "            i,j,k = i+1,j+1,k+1\n",
    "        # 如果 k != n 说明末尾有空余，这段空余无法匹配\n",
    "        # 如果 k == n 那么i指向第二段的首位置，j指向第三段的首位置\n",
    "        if k == n:\n",
    "            return [i-1,j]\n",
    "        else:\n",
    "            return [-1,-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3: return [-1, -1]\n",
    "        if s == 0: return [0, 2]\n",
    "        partial =  s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == partial + partial:\n",
    "                    third = i\n",
    "                cur += 1 #记录1的个数\n",
    "        n = len(arr)\n",
    "        lenth = n - third\n",
    "        if first + lenth <= second and second + lenth <= third:\n",
    "            for i in range(0, n - third, 1):\n",
    "                if arr[first + i] != arr[second + i] or arr[second + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "            return [first + lenth - 1, second + lenth]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        def find(x):\n",
    "            s = 0\n",
    "            for i, v in enumerate(arr):\n",
    "                s += v\n",
    "                if s == x:\n",
    "                    return i\n",
    "        n = len(arr)\n",
    "        cnt, mod = divmod(sum(arr), 3)\n",
    "        if mod:\n",
    "            return [-1, -1]\n",
    "        if cnt == 0:\n",
    "            return [0, n - 1]\n",
    "        i, j, k = find(1), find(cnt + 1), find(cnt * 2 + 1)\n",
    "        while k < n and arr[i] == arr[j] == arr[k]:\n",
    "            i, j, k = i + 1, j + 1, k + 1\n",
    "        return [i-1, j] if k == n else [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        \n",
    "        one_nums = sum(arr)\n",
    "        if one_nums % 3 != 0:\n",
    "            return [-1, -1]\n",
    "        if one_nums == 0:\n",
    "            return [0, len(arr)-1]\n",
    "\n",
    "        n, cnt = len(arr), 0\n",
    "        \n",
    "        for i in range(n):\n",
    "\n",
    "            if arr[i] == 1:\n",
    "                if cnt == 0:\n",
    "                    loc1 = i\n",
    "                elif cnt == one_nums // 3:\n",
    "                    loc2 = i\n",
    "                elif cnt == one_nums // 3 * 2:\n",
    "                    loc3 = i\n",
    "                cnt += 1\n",
    "\n",
    "        length = n - loc3\n",
    "        if loc1 + length > loc2 or loc2 + length > loc3:\n",
    "            return [-1, -1]\n",
    "        if not (arr[loc1:(loc1 + length)] == arr[loc2:(loc2 + length)] == arr[loc3:]):\n",
    "            return [-1, -1]\n",
    "        return [loc1 + length - 1, loc2 + length]      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        cnt = Counter(arr)\n",
    "        if cnt[1] % 3:\n",
    "            return [-1,-1]\n",
    "        cnt = cnt[1] // 3\n",
    "        n = len(arr)\n",
    "        if cnt == 0:\n",
    "            return [0,n - 1]\n",
    "        # 找到第idx个1\n",
    "        def find(idx):\n",
    "            for i,x in enumerate(arr):\n",
    "                if x:\n",
    "                    idx -= 1\n",
    "                    if idx == 0:\n",
    "                        return i\n",
    "        i,j,k = find(1),find(cnt + 1),find(cnt*2 + 1)\n",
    "        while k < n and arr[i] == arr[j] == arr[k]:\n",
    "            i += 1\n",
    "            j += 1\n",
    "            k += 1\n",
    "        return [i - 1,j] if k == n else [-1,-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        if s == 0:\n",
    "            return [0, 2]\n",
    "\n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == 2 * partial:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "        #print(first, second, third)\n",
    "        n = len(arr)\n",
    "        length = n - third\n",
    "        if first + length <= second and second + length <= third:\n",
    "            i = 0\n",
    "            while third + i < n:\n",
    "                if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + length - 1, second + length]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3: return [-1, -1]\n",
    "        if s == 0: return [0, 2]\n",
    "        partial =  s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == partial + partial:\n",
    "                    third = i\n",
    "                cur += 1 #记录1的个数\n",
    "        n = len(arr)\n",
    "        lenth = n - third\n",
    "        if first + lenth <= second and second + lenth <= third:\n",
    "            for i in range(0, n - third, 1):\n",
    "                if arr[first + i] != arr[second + i] or arr[second + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "            return [first + lenth - 1, second + lenth]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        first, second, third = 0, 0, 0\n",
    "        n = len(arr)\n",
    "        N = arr.count(1)\n",
    "        if N % 3: return [-1, -1]\n",
    "        if N == 0: return [0, n-1]\n",
    "        cishu = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                cishu += 1\n",
    "            else:\n",
    "                continue\n",
    "            if cishu == 1:\n",
    "                first = i\n",
    "            elif cishu == N // 3 + 1:\n",
    "                second = i\n",
    "            elif cishu == N // 3 * 2 + 1:\n",
    "                third = i\n",
    "        #print(N, first, second, third)\n",
    "        while third < n:\n",
    "            first += 1\n",
    "            second += 1\n",
    "            third += 1\n",
    "            if third < n and (arr[first] != arr[second] or arr[second] != arr[third]):\n",
    "                break\n",
    "        if third < n:\n",
    "            return [-1, -1]\n",
    "        return [first-1, second]\n",
    "# class Solution:\n",
    "#     def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "#         first, second, third = 0, 0, 0\n",
    "#         n = len(arr)\n",
    "#         N = arr.count(1)\n",
    "#         if N % 3: return [-1, -1]\n",
    "#         if N == 0: return [0,n-1]\n",
    "#         cishu = 0\n",
    "#         for i in range(n):\n",
    "#             if arr[i] == 1:\n",
    "#                 cishu += 1\n",
    "#             else:\n",
    "#                 continue\n",
    "#             if cishu == 1:\n",
    "#                 first = i\n",
    "#             elif cishu == N // 3 + 1:\n",
    "#                 second = i\n",
    "#             elif cishu == N // 3 * 2 + 1:\n",
    "#                 third = i\n",
    "#         print(N, first, second, third)\n",
    "#         for k in range(1, n - third):\n",
    "#             if arr[first + k] != arr[second + k] or arr[second + k] != arr[third + k]:\n",
    "#                 return [-1,-1]\n",
    "#         return [first + n - third -1, second + n - third]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        need = s // 3 \n",
    "        breaks = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                cnt += 1 \n",
    "                if cnt in (1, need + 1, 2 * need + 1):\n",
    "                    breaks.append(i)\n",
    "                if cnt in (need, need * 2, need * 3):\n",
    "                    breaks.append(i)\n",
    "        if len(breaks) != 6:\n",
    "            return [0, n - 1]\n",
    "        x1, y1, x2, y2, x3, y3 = breaks\n",
    "        if n - y3 > x2 - y1 or n - y3 > x3 - y2 or not arr[x1 : y1 + 1] == arr[x2 : y2 + 1] == arr[x3 : y3 + 1]:\n",
    "            return [- 1, - 1]\n",
    "        return [y1 + n - y3 - 1, y2 + n - y3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "\n",
    "        cnt1 = arr.count(1)\n",
    "        if cnt1 == 0:\n",
    "            return [0, 2]\n",
    "        if cnt1 % 3:\n",
    "            return [-1, -1]\n",
    "        avg = cnt1 // 3\n",
    "        first = second = third = cur = 0\n",
    "        n = len(arr)\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == avg:\n",
    "                    second = i\n",
    "                elif cur == avg * 2:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "        \n",
    "        i = 0\n",
    "        length = n - third\n",
    "        while third + i < n:\n",
    "            if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:\n",
    "                return [-1, -1]\n",
    "            i += 1\n",
    "        \n",
    "        return [first + length - 1, second + length]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        ones = sum(arr)\n",
    "        if ones % 3:\n",
    "            return [-1, -1]\n",
    "        if not ones:\n",
    "            return [0, 2]\n",
    "        each, a, b, c, cnts = ones // 3, -1, -1, -1, 0\n",
    "        for idx, v in enumerate(arr):\n",
    "            if v:\n",
    "                cnts += 1\n",
    "            if a == -1 and cnts:\n",
    "                a = idx\n",
    "            if b == -1 and cnts > each:\n",
    "                b = idx\n",
    "            if cnts > each * 2:\n",
    "                c = idx\n",
    "                break\n",
    "        if (length := len(arr) - c) and arr[c:] == arr[a:a+length] == arr[b:b+length]:\n",
    "            return [a + length - 1, b + length]\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        def equal(a_list, b_list, c_list):\n",
    "            a = b = c = 0\n",
    "            for i in range(len(a_list)):\n",
    "                a = a * 2 + a_list[i]\n",
    "            for i in range(len(b_list)):\n",
    "                b = b * 2 + b_list[i]\n",
    "            for i in range(len(c_list)):\n",
    "                c = c * 2 + c_list[i]\n",
    "            if a == b and b == c:\n",
    "                return True\n",
    "            else:\n",
    "                return False    \n",
    "        if not sum(arr) % 3 == 0:\n",
    "            return [-1, -1]\n",
    "        n = sum(arr) // 3\n",
    "        if n == 0:\n",
    "            return [0, len(arr)-1]\n",
    "        num = 0\n",
    "        one_index = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i] == 1:\n",
    "                num += 1\n",
    "                if num % n == 0:\n",
    "                    one_index.append(i)\n",
    "        zero_count = 0\n",
    "        t = -1\n",
    "        while(arr[t] == 0):\n",
    "            zero_count += 1\n",
    "            t -= 1\n",
    "        first_list = arr[:one_index[0]+zero_count+1]\n",
    "        second_list = arr[one_index[0]+zero_count+1: one_index[1]+zero_count+1]\n",
    "        thrid_list = arr[one_index[1]+zero_count+1:]\n",
    "        if equal(first_list, second_list, thrid_list):\n",
    "            return [one_index[0]+zero_count, one_index[1]+zero_count+1]  \n",
    "        else:\n",
    "            return [-1, -1]          \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3: return [-1, -1]\n",
    "        if s == 0: return [0, 2]\n",
    "        partial =  s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == partial + partial:\n",
    "                    third = i\n",
    "                cur += 1 #记录1的个数\n",
    "        n = len(arr)\n",
    "        lenth = n - third\n",
    "        if first + lenth <= second and second + lenth <= third:\n",
    "            i = 0\n",
    "            while third + i < n:\n",
    "                if arr[first + i] != arr[second + i] or arr[second + i] != arr[third + i]: return [-1, -1]\n",
    "                i += 1\n",
    "            return [first + lenth - 1, second + lenth]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        need = s // 3 \n",
    "        breaks = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                cnt += 1 \n",
    "                if cnt in (1, need + 1, 2 * need + 1):\n",
    "                    breaks.append(i)\n",
    "                if cnt in (need, need * 2, need * 3):\n",
    "                    breaks.append(i)\n",
    "        if len(breaks) != 6:\n",
    "            return [0, n - 1]\n",
    "        x1, y1, x2, y2, x3, y3 = breaks\n",
    "        if n - y3 > x2 - y1 or n - y3 > x3 - y2 or not arr[x1 : y1 + 1] == arr[x2 : y2 + 1] == arr[x3 : y3 + 1]:\n",
    "            return [- 1, - 1]\n",
    "        return [y1 + n - y3 - 1, y2 + n - y3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        s = sum(arr)\n",
    "        if s % 3: return [-1, -1]\n",
    "        if s == 0: return [0, 2]\n",
    "        partial =  s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            if x:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == partial + partial:\n",
    "                    third = i\n",
    "                cur += 1 #记录1的个数\n",
    "        n = len(arr)\n",
    "        lenth = n - third\n",
    "        if first + lenth <= second and second + lenth <= third:\n",
    "            for i in range(0, n - third, 1):\n",
    "                if arr[first + i] != arr[second + i] or arr[second + i] != arr[third + i]:\n",
    "                    return [-1, -1]\n",
    "            return [first + lenth - 1, second + lenth]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        # def check(x,y,z):\n",
    "        #     high_bit = max(len(x),len(y),len(z))\n",
    "        #     for i in range(high_bit,-1,-1):\n",
    "        #         if (x >> i)&1 != (y >> i)&1 or (x >> i)&1 != (z >> i) & 1 or (y >> i)&1 != (z >> i) & 1:\n",
    "        #             return False\n",
    "        # # 枚举i,j\n",
    "        # n = len(arr)\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+2,n):\n",
    "        #         if check(arr[:i+1],arr[i+1:j],arr[j+1:]):\n",
    "        #             return [i,j]\n",
    "        # return [-1,-1]\n",
    "\n",
    "\n",
    "        s = sum(arr)\n",
    "        if s%3:\n",
    "            return [-1,-1]\n",
    "        if s == 0:\n",
    "            return [0,2]\n",
    "        partial = s // 3\n",
    "        first = second = third = cur = 0\n",
    "        for i,v in enumerate(arr):\n",
    "            if v:\n",
    "                if cur == 0:\n",
    "                    first = i\n",
    "                elif cur == partial:\n",
    "                    second = i\n",
    "                elif cur == 2*partial:\n",
    "                    third = i\n",
    "                cur += 1\n",
    "        # 统计完 first，second，third之后\n",
    "        n = len(arr)\n",
    "        leave = n - third\n",
    "        if first + leave <= second and second + leave <= third:\n",
    "            # 从前往后面判断是否相等\n",
    "            i = 0\n",
    "            while third + i < n:\n",
    "                if arr[first+i] != arr[second+i] or arr[first+i] != arr[third+i]:\n",
    "                    return [-1,-1]\n",
    "                i += 1\n",
    "            return [first + leave-1,second + leave]\n",
    "        return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        ones = sum(arr)\n",
    "        if ones % 3:\n",
    "            return [-1, -1]\n",
    "        if not ones:\n",
    "            return [0, 2]\n",
    "        each, a, b, c, cnts = ones // 3, -1, -1, -1, 0\n",
    "        for idx, v in enumerate(arr):\n",
    "            if v:\n",
    "                cnts += 1\n",
    "            if a == -1 and cnts:\n",
    "                a = idx\n",
    "            if b == -1 and cnts > each:\n",
    "                b = idx\n",
    "            if cnts > each * 2:\n",
    "                c = idx\n",
    "                break\n",
    "        if (length := len(arr) - c) and arr[c:] == arr[a:a+length] == arr[b:b+length]:\n",
    "            return [a + length - 1, b + length]\n",
    "        return [-1, -1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        need = s // 3 \n",
    "        breaks = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                cnt += 1 \n",
    "                if cnt in (1, need + 1, 2 * need + 1):\n",
    "                    breaks.append(i)\n",
    "                if cnt in (need, need * 2, need * 3):\n",
    "                    breaks.append(i)\n",
    "        if len(breaks) != 6:\n",
    "            return [0, n - 1]\n",
    "        x1, y1, x2, y2, x3, y3 = breaks\n",
    "        if n - y3 > x2 - y1 or n - y3 > x3 - y2 or not arr[x1 : y1 + 1] == arr[x2 : y2 + 1] == arr[x3 : y3 + 1]:\n",
    "            return [- 1, - 1]\n",
    "        return [y1 + n - y3 - 1, y2 + n - y3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        s = sum(arr)\n",
    "        if s % 3:\n",
    "            return [-1, -1]\n",
    "        need = s // 3 \n",
    "        breaks = []\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                cnt += 1 \n",
    "                if cnt in (1, need + 1, 2 * need + 1):\n",
    "                    breaks.append(i)\n",
    "                if cnt in (need, need * 2, need * 3):\n",
    "                    breaks.append(i)\n",
    "        if len(breaks) != 6:\n",
    "            return [0, n - 1]\n",
    "        x1, y1, x2, y2, x3, y3 = breaks\n",
    "        if n - y3 > x2 - y1 or n - y3 > x3 - y2 or not arr[x1 : y1 + 1] == arr[x2 : y2 + 1] == arr[x3 : y3 + 1]:\n",
    "            return [- 1, - 1]\n",
    "        return [y1 + n - y3 - 1, y2 + n - y3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        if n == 3: return [0,2] if (arr[0] == arr[1] == arr[2]) else [-1,-1]\n",
    "        i, j = 0, n -1\n",
    "        prev, mid, post = arr[0], 0, arr[-1]\n",
    "        for k in range(i+1, j):\n",
    "            mid = mid * 2 + arr[k]\n",
    "\n",
    "        while i+2 < j:\n",
    "            while i+2 < j and (prev < post or arr[i] != arr[-1]):\n",
    "                i += 1\n",
    "                prev = prev * 2 + arr[i]\n",
    "                if arr[i]: mid ^= (1 << (j-i-1))\n",
    "\n",
    "            while post < prev and i+2 < j:\n",
    "                j -= 1\n",
    "                if arr[j]: post += (1 << (n-j-1))\n",
    "                mid //= 2\n",
    "\n",
    "            if prev == mid == post: return [i, j]\n",
    "            if mid < min(prev, post): break\n",
    "            if prev == post:\n",
    "                while i+2 < j and arr[j-1] == 0:\n",
    "                    j -= 1\n",
    "                    mid //= 2\n",
    "                    if mid == post: return [i, j]\n",
    "                if i+2 == j: break\n",
    "                j -= 1\n",
    "                post += (1 << (n - j - 1))\n",
    "                mid //= 2\n",
    "\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, a: List[int]) -> List[int]:\n",
    "        \n",
    "        def solve(a):\n",
    "            n = len(a)\n",
    "            for k in range(n//3+1):\n",
    "                # print(k)\n",
    "                j = k+1\n",
    "                while j<n and a[j]==0:\n",
    "                    j+=1\n",
    "                if j+k+1>n or a[:k+1]!=a[j:j+k+1]:\n",
    "                    continue\n",
    "                i = j+k+1\n",
    "                while i<n and a[i]==0:\n",
    "                    i+=1\n",
    "                if i+k+1>n or a[j:j+k+1]!=a[i:i+k+1] or i+k+1!=n:\n",
    "                    continue\n",
    "                return [k, j+k+1]\n",
    "            return [-1, -1]\n",
    "        shift = 0\n",
    "        for i in range(len(a)):\n",
    "            if a[i]==1:\n",
    "                break\n",
    "            shift+=1\n",
    "        if shift==len(a):\n",
    "            return [0, len(a)-1]\n",
    "        a = a[shift:]\n",
    "        i, j = solve(a)\n",
    "        if i==-1:\n",
    "            return [-1, -1]\n",
    "        return [i+shift, j+shift]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        n, ones = len(arr), []\n",
    "        for i, v in enumerate(arr):\n",
    "            if v == 1: ones.append(i)\n",
    "        cnt = len(ones)\n",
    "        if cnt % 3 != 0: return [-1, -1]\n",
    "        if not ones: return [0, 2]\n",
    "        m = cnt // 3\n",
    "        i1, i2, i3 = ones[0], ones[m], ones[2 * m]\n",
    "        while i3 < n:\n",
    "            if arr[i1] == arr[i2] == arr[i3]:\n",
    "                i1 += 1\n",
    "                i2 += 1\n",
    "                i3 += 1\n",
    "            else: return [-1, -1]\n",
    "        return [i1 - 1, i2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        ones = []\n",
    "        n = len(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i] == 1:\n",
    "                ones.append(i)\n",
    "        m = len(ones)\n",
    "        if m % 3 :\n",
    "            return [-1,-1]\n",
    "        elif m == 0:\n",
    "            return [0,2]\n",
    "        for i in range(m//3-1,0,-1):\n",
    "            j = m//3 + i\n",
    "            k = m//3 + j\n",
    "            if ones[i] - ones[i-1] != ones[j]-ones[j-1] or ones[j]-ones[j-1] != ones[k] - ones[k-1]:\n",
    "                return [-1,-1]\n",
    "        if n - ones[-1] <= ones[m//3]-ones[m//3-1] and n - ones[-1] <= ones[2*m//3]-ones[2*m//3-1]:\n",
    "            return [ones[m//3-1] + n - ones[-1] - 1,ones[2*m//3-1]+ n - ones[-1] ]\n",
    "        else:\n",
    "            return [-1,-1]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        if 1 not in arr: return [0,2]\n",
    "        if arr.count(1) % 3 != 0: return [-1,-1]\n",
    "        arr_new = [i for i in range(len(arr)) if arr[i] == 1]\n",
    "        a = arr_new[0]\n",
    "        b = arr_new[arr.count(1)//3]\n",
    "        c = arr_new[-arr.count(1)//3]\n",
    "        if arr[a:a+len(arr)-c] == arr[b:b+len(arr)-c] == arr[c:len(arr)]:\n",
    "            return [arr.index(1) + len(arr)-c -1, b + len(arr)-c]\n",
    "        else:\n",
    "            return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        if 1 not in arr: return [0,2]\n",
    "        if arr.count(1) % 3 != 0: return [-1,-1]\n",
    "        arr_new = [j for j,i in enumerate(arr) if i == 1]\n",
    "        a = arr_new[0]\n",
    "        b = arr_new[arr.count(1)//3]\n",
    "        c = arr_new[-arr.count(1)//3]\n",
    "        for i in range(len(arr)-c):\n",
    "            if arr[c+i] == arr[b+i] == arr[a+i]:\n",
    "                continue\n",
    "            else:\n",
    "                return [-1, -1]\n",
    "        return [arr.index(1) + len(arr)-c -1, b + len(arr)-c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        if 1 not in arr: return [0,2]\n",
    "        if arr.count(1) % 3 != 0: return [-1,-1]\n",
    "        arr_new = [j for j,i in enumerate(arr) if i == 1]\n",
    "        a = arr_new[0]\n",
    "        b = arr_new[arr.count(1)//3]\n",
    "        c = arr_new[-arr.count(1)//3]\n",
    "        if arr[a:a+len(arr)-c] == arr[b:b+len(arr)-c] == arr[c:len(arr)]:\n",
    "            return [arr.index(1) + len(arr)-c -1, b + len(arr)-c]\n",
    "        else:\n",
    "            return [-1,-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def threeEqualParts(self, arr: List[int]) -> List[int]:\n",
    "        counter=Counter(arr)\n",
    "        if counter[1]%3!=0:\n",
    "            return [-1,-1]\n",
    "        if counter[1]==0:\n",
    "            return [0,2]\n",
    "        per_l=counter[1]//3\n",
    "        per_l_end0=-1\n",
    "        t=0\n",
    "        first=''\n",
    "        suffix_count=0\n",
    "        for i,e in enumerate(arr):\n",
    "            if e==1 or first:\n",
    "                if per_l_end0==-1:\n",
    "                    first+=str(e)\n",
    "            if e==1:\n",
    "                t+=1\n",
    "            if t==per_l and per_l_end0==-1:\n",
    "                per_l_end0=i    \n",
    "            if per_l_end0!=-1:\n",
    "                if e==0:\n",
    "                    suffix_count+=1\n",
    "                elif per_l_end0!=i:\n",
    "                    break\n",
    "       # print(first,suffix_count,per_l_end0)\n",
    "        of=first\n",
    "        for c in range(suffix_count+1):\n",
    "            if 3*(len(of)+c)>len(arr):\n",
    "                break\n",
    "            \n",
    "            first=of+'0'*c   \n",
    "            if arr[-len(first)]==0:\n",
    "                continue\n",
    "            second=''.join(map(str,arr[per_l_end0+suffix_count+1:per_l_end0+suffix_count+1+len(first)]))\n",
    "            \n",
    "            if first!=second:\n",
    "                continue\n",
    "            third=''.join(map(str,arr[-len(first):]))\n",
    "           # print(first,second,third)\n",
    "            if first==third:\n",
    "                return [per_l_end0+c,per_l_end0+suffix_count+len(first)+1]\n",
    "        return [-1,-1]\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
